#include <stdio.h>
#include <vector>
#include <stdlib.h>
#include <time.h>
void print_arr(const std::vector<int>& vec)
{
    int n = vec.size();
    for(int i = 0; i < n - 1; i ++)
    {
        printf("%d->", vec[i]);
    }
    printf("%d\n", vec[n-1]);
}
void swap(std::vector<int>& arr, int i ,int j)
{
    if(i == j)
    {
        return;
    }
    arr[i] ^= arr[j];
    arr[j] ^= arr[i];
    arr[i] ^= arr[j];
}
int partition(std::vector<int>& arr, int left, int right)
{
    int index = left + rand() % (right - left);
    swap(arr,left, index);
    int pv = arr[left];
    int i = left + 1;
    int j = right;
    while(true)
    {
        while(i <= right && arr[i] < pv)
        {
            i++;
        }
        while(j > left && arr[j] > pv)
        {
            j--;
        }
        if(i >= j)
        {
            break;
        }
        swap(arr, i, j);
        i++;
        j--;
    }
    swap(arr, left, j);
    return j;
}
void _qsort(std::vector<int>& arr, int left, int right)
{
    srand(time(NULL));
    if(left >= right)
    {
        return;
    }
    int p = partition(arr, left, right);
    _qsort(arr, left, p - 1);
    _qsort(arr, p+1, right);
}
void qsort(std::vector<int>& arr)
{
    _qsort(arr, 0, arr.size()-1);
}
int main()
{
    int arr[] = {9,3,1,0,4,5,2,8};
    std::vector<int> vec(arr, arr + sizeof(arr)/ sizeof(*arr));
    print_arr(vec);
    qsort(vec);
    print_arr(vec);
    return 0;
}
